package main

import "fmt"

/*
从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。（注意是一行一行输出）
思路：使用两个TreeNode类型的变量last和nlast来解决，last代表当前行中的最后一个元素，nlast代表下一行中的最后一个元素
	  当遍历到了last时，让last=nlast，然后开始下一行的遍历
	  其中，nlast如何获取是一个注意的地方，nlast只需要一直记录最新加入队列中的节点即可，
	  当遍历到了last的时候，nlast就一定是下一行的最后一个元素
*/

type TreeNode struct {
	val       int
	leftNode  *TreeNode
	rightNode *TreeNode
}

func main() {
	//        8
	//       / \
	//      3   10
	//     /\   / \
	//    1  6     14
	//   /\  /\    /
	//      4  7  13
	root := TreeNode{val: 8}
	root.leftNode = &TreeNode{val: 3}
	root.rightNode = &TreeNode{val: 10}
	root.leftNode.leftNode = &TreeNode{val: 1}
	root.leftNode.rightNode = &TreeNode{val: 6}
	root.leftNode.rightNode.leftNode = &TreeNode{val: 4}
	root.leftNode.rightNode.rightNode = &TreeNode{val: 7}
	root.rightNode.rightNode = &TreeNode{val: 14}
	root.rightNode.rightNode.leftNode = &TreeNode{val: 13}

	printAsLines(&root)
}

func printAsLines(root *TreeNode) {
	if root == nil {
		return
	}

	var queue []*TreeNode
	var layerList []int
	var last *TreeNode
	var nlast *TreeNode

	queue = append(queue, root)
	last = root
	for len(queue) != 0 {
		node := queue[0]
		layerList = append(layerList, node.val)
		queue = queue[1:]
		if node.leftNode != nil {
			queue = append(queue, node.leftNode)
			nlast = node.leftNode
		}
		if node.rightNode != nil {
			queue = append(queue, node.rightNode)
			nlast = node.rightNode
		}

		if node == last {
			fmt.Println(layerList)
			layerList = nil
			last = nlast
		}
	}
}
